LeetCode——Pow(x,n)

NO.50 Pow(x,n) 中等

思路一：暴力法 这道题暴力法是不能通过leetcode判题机，会得到一个t。但是方法本身是可以得到正确答案的，所以我们需要对他进行优化。暴力法的想法很简单的：2^3=2*2*2。

如果n为负，则n=-n同时x=1/x，例如2^(-3)=1/2*1/2*1/2。但是这里要注意n的取值范围，主要是 正整数和负整数的不同范围限制 。

public double myPow(double x, int n) {
    if (x==0)return 0;
    if (n==0)return 1;
    double ans=1;
    long N=n;
    if (N<0){
        N=-N;
        x=1/x;
    }
    for (int i=0;i<N;i++){
        ans*=x;
    }
    return ans;
}

时间复杂度：O(n)

思路二：二分法 当我们得到x^(n/2)的时候，我们不需要再去乘上n/2个x了，而是x^(n/2)*x^(n/2)=x^n。

这个想法用递归很容易实现，但是需要注意的是n的奇偶性，如果n为奇数则需要再乘上一个x。

public double myPow(double x, int n) {
    switch (n){
        case 1:return x;
        case 0:return 1;
        case -1:return 1/x;
    }
    double half=myPow(x,n/2);
    //奇偶性处理
    double rest=myPow(x,n%2);
    return half*half*rest;
}

时间复杂度：O(logn)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github